The present invention relates to the process of scheduling jobs in a multiprocessor system.
To fully utilize the processing power of a multiprocessor system, it is important to schedule jobs properly. Conventionally, in a single-processor system, an earliest-deadline-first (EDF) approach can schedule all the jobs without missing any deadlines if such a system is underloaded. In an overloaded single-processor system, scheduling schemes based on Time Utility Functions perform better than EDF approaches, because such schemes typically attempt to maximize the total utility accrued by the system. However, although these approaches are viable solutions in single-processor systems, they become inadequate in a multiprocessor system where a job may request a number of CPUs for its processing.
The challenge of scheduling jobs requesting multiple CPUs often arises in multiprocessor systems, such as massively parallel computing systems, Grid systems, and data centers. One approach to meet this challenge is to use a greedy scheduling scheme, which inserts as many high-utility jobs into the schedule as early as possible. Such greedy schemes assume that the future performance of the system is unpredictable, and that it is therefore better to maximize the current benefit to the system based on current job utility. However, sometimes reducing the current job utility may help the system accrue better long-term utility. Therefore, a greedy approach may not achieve the best long-term accrued utility because it only maximizes instantaneous utility.